14.5 チャネル - garbage-collection

14.5 チャネル

高コストな不可分命令を使わなくてもいい分散方法。

1スレッドが書きこみ1スレッドが読み出すようなチャネルを使ってスレッド間でマーク処理を交換する(ref: アルゴリズム13-34)

code:14-7.py

shared channelN, N

me = myThreadID

def acquireWork():

for each k in Threads

if not isEmpty(channelk, me): # スレッドkが仕事を送ってきている。

ref = remove(channelk, me)

push(myMarkStack, ref)

return

def performWork():

while True:

if isEmpty(myMarkStack):

return # 仕事はない。

ref = pop(myMarkStack) # これなんでqueueではない必要がある？ stackであることが必要？ → そうしたほうがキャッシュ的に嬉しいから？

for each fld in pointers(ref):

child = *fld

if child != null && not isMarked(child):

if not generateWork(child):

push(myMarkStack, child) # ↓ つまり渡せなかったら自分でやる。

def generateWork(ref): # 渡すことに成功したかどうかを返す。

for each j in Threads:

if needWork(j) && not isFull(channelme, j):

add(channelme, j, ref)

return true

return false

積極的に他のスレッドに仕事を渡すようにすることによって、休んでいるスレッドがあまり出ないようにしている。

長さ1か2のキューがWuとLiの報告によれば最もよくスケールした。